package com.Floyd;

import java.util.ArrayList;
import java.util.List;

public class Floyd {
  
     //dist[i][j]=INF<==>no edges between i and j
     //the distance between i and j.At first,dist[i][j] 
     //is the weight of edge [i,j]
     private int[][] dist;
  
     private int[][] path; 
     
     private int m=Integer.MAX_VALUE;
     
     private List<Integer> resultLine=new ArrayList<Integer>();
	
     public Floyd(int size){
 		this.path=new int[size][size];
 		this.dist=new int[size][size];
 	}
     
	public  void findCheapestPath(int begin,int end,int[][] matrix){
		floyd(matrix);	
		resultLine.add(begin);
		findPath(begin,end);
		resultLine.add(end);
	}
	
	public void findPath(int i,int j){
		int k=path[i][j];
		if(k==-1)return;
		findPath(i,k);
		resultLine.add(k);
		findPath(k,j);
	}
	
	public  void floyd(int[][] matrix){
		int size=matrix.length;
		//initialize dist and path
		for(int i=0;i<size;i++){
			for(int j=0;j<size;j++){
				path[i][j]=-1;
				dist[i][j]=matrix[i][j];
			}
		}
		for(int i=0;i<size;i++){
			for(int j=0;j<size;j++){
				for(int k=0;k<size;k++){
					if( dist[i][k]!=m && dist[k][j]!=m
					     && dist[i][k]+dist[k][j]<dist[i][j])//dist[i][k]+dist[k][j]>dist[i][j]-->longestPath
					{ 
						dist[i][j]=dist[i][k]+dist[k][j];
						path[i][j]=k;
					}
				}
			}
		}	
	}
	//getter 
	public int[][] getDist() {
		return dist;
	}
	public List<Integer> getResultLine() {
		return resultLine;
	}
}
